package com.zrkizzy.doublepointer;

import java.util.ArrayList;
import java.util.List;

/**
 * 151. 反转字符串中的单词
 *
 * @author zhangrongkang
 * @see <a href="https://leetcode.cn/problems/reverse-words-in-a-string/description/">https://leetcode.cn/problems/reverse-words-in-a-string/description/</a>
 * @since 2022/11/28
 */
public class 反转字符串中的单词 {

    class Solution01 {
        public String reverseWords(String s) {
            // 去除字符串首位的空格
            s = s.trim();
            // 定义双指针的初值
            int left = s.length() - 1, right = s.length();
            // 定义返回的结果集
            StringBuilder builder = new StringBuilder();

            while (left >= 0) {
                // 寻找第一个出现的空格（防止越界）
                while (left >= 0 && s.charAt(left) != ' ') {
                    left--;
                }
                // 截取当前的字符串
                builder.append(s.substring(left + 1, right)).append(" ");
                // 移动左指针
                while (left >= 0 && s.charAt(left) == ' ') {
                    left--;
                }
                // 移动右指针
                right = left + 1;
            }
            // 去除最后的空格
            builder.deleteCharAt(builder.length() - 1);
            // 返回结果
            return builder.toString();
        }
    }

    class Solution02 {
        public String reverseWords(String s) {
            // 去除字符串首位的空格
            s = s.trim();
            // 越界判断
            if (s.length() < 2) {
                return s;
            }
            // 定义双指针的初值
            int left = -1, right = 0;
            // 定义辅助集合
            List<String> list = new ArrayList<>();

            while (right <= s.length() - 1) {
                // 移动右指针找到第一个空格位置
                while (right <= s.length() - 1 && s.charAt(right) != ' ') {
                    right++;
                }
                // 截取字符串并添加到集合中
                list.add(s.substring(left + 1, right));
                // 移动右指针
                while (right <= s.length() - 1 && s.charAt(right) == ' ') {
                    right++;
                }
                // 移动左指针
                left = right - 1;
            }
            StringBuilder builder = new StringBuilder();
            for (int i = list.size() - 1; i >= 0; i--) {
                builder.append(list.get(i)).append(" ");
            }
            // 去除最后的空格
            builder.deleteCharAt(builder.length() - 1);
            return builder.toString();
        }
    }

}
